struct SplayTree{ // 伸展树维护区间数据, 有效区间[1...n], 操作前要init && build

using llt = long long;

using data_type = llt;  // 本身的数据类型
using value_type = llt; // 维护信息的类型
using lazy_type = llt;  // 延迟标记类型

static int const LEFT = 0;
static int const RIGHT = 1;

struct node_t { // 节点的类型 
    int parent;
    int son[2];
	int size;   // size域, 子树的节点数量
	data_type data;   // 本身的数据
	int flip;         // 翻转标记，也是延迟标记的一种
	value_type value; // 维护信息
	lazy_type lazy;   // 延迟标记
};

int Root;
vector<node_t> Nodes; // 0表示NULL且Nodes[0]中保证全是0
int toUsed;

// 从下往上计算value，用于pushUp,伸展树应保证ls与rs均有意义
value_type _up_(const value_type & ls, const value_type & rs) {
	assert(0);
}

// 根据变动信息delta计算本节点的信息并且打延迟标记，用于pushDown或者modify
// flip其实也是延迟标记的一部分，这里只计算t，跟t的儿子无关
// 要维护t的data、value和lazy、flip
void _dn_(int t, const lazy_type & delta, int flip) {
	assert(0);
}

/// 根据给定的data生成维护的信息
static value_type mkValue(const data_type & data) {
	assert(0);
}

static const value_type value_zero() {
	static const value_type VALUE_0 = 0;
	return VALUE_0;
}

static const lazy_type lazy_zero() {
	static const lazy_type LAZY_0 = 0;
	return LAZY_0;
}

static const data_type data_zero() {
	static const data_type DATA_0 = 0;
	return DATA_0;
}

// 返回节点t的排行, 保证不对树根调用
int _sn(int t) {
	assert(t != Root);
	return Nodes[Nodes[t].parent].son[LEFT] == t ? LEFT : RIGHT;
}

// 根据t节点的儿子，计算t节点
void _pushUp(int t) {
	Nodes[t].size = 1;
	Nodes[t].value = mkValue(Nodes[t].data);
    int son = Nodes[t].son[LEFT];
	if(son) {
		Nodes[t].size += Nodes[son].size;
		Nodes[t].value = _up_(Nodes[son].value, Nodes[t].value);
	}
	son = Nodes[t].son[RIGHT];
	if(son) {
		Nodes[t].size += Nodes[son].size;
		/// 必须t在左、右儿子在右
		Nodes[t].value = _up_(Nodes[t].value, Nodes[son].value);
	}
	return;
}

// 根据t的延迟去计算t的儿子
void _pushDown(int t) {
	auto & n = Nodes[t];
    if(n.lazy == lazy_zero() and n.flip == 0) return;
	
	int son;
	auto & lz = n.lazy;
	auto flip = n.flip;
	if(son = Nodes[t].son[LEFT]) _dn_(son, lz, flip);
	if(son = Nodes[t].son[RIGHT]) _dn_(son, lz, flip);

	lz = lazy_zero();
	n.flip = 0;
	return;
}

// 分配一个新节点，初始化value和size，其余均为零
int _newNode(const data_type & data) {
	auto & n = Nodes[++toUsed];
	assert(toUsed < Nodes.size());
	n.value = mkValue(n.data = data);
	n.size = 1;
	return toUsed;
}

// 将parent的sn儿子设置为son
void _link(int parent, int sn, int son) {
    Nodes[Nodes[parent].son[sn] = son].parent = parent;
}

// 旋转操作, t不能是树根
void _rotate(int t) {
    assert(t != Root);
	int p = Nodes[t].parent;
	int sn = _sn(t);
	int osn = sn ^ 1;

	// 如果splay紧跟kth调用，则此处无需pushDown
	// 重新确定三对父子关系
	_link(p, sn, Nodes[t].son[osn]);
	if(p != Root) _link(Nodes[p].parent, _sn(p), t);
	else Nodes[t].parent = 0;
	_link(t, osn, p);
	// 只维护p即可
	_pushUp(p);
}

// 将t伸展为p的儿子，如果p为0则将t伸展为树根
void _splay(int p, int t) {
    int pp;
	while((pp = Nodes[t].parent) != p) {
		if(Nodes[pp].parent != p) {
			_sn(pp) == _sn(t) ? _rotate(pp) : _rotate(t);
		}
		_rotate(t);
	}
	_pushUp(t); // 最后维护t
	if(0 == p) Root = t;
	return;
}

// 在t子树上找第k个元素，从0开始
// 这是一个内部函数，考虑了哨兵的影响，因此从0开始
int _kth(int t, int k) {
    assert(0 <= k and k < Nodes[t].size);
	_pushDown(t);
	int son = Nodes[t].son[LEFT];
	int s = son ? Nodes[son].size : 0;
	if(k < s) return _kth(son, k);
	return s < k ? _kth(Nodes[t].son[RIGHT], k - s - 1) : t;
}

void _build(int & t, int parent, int sn, int s, int e, const data_type a[]) {
	int mid = (s + e) >> 1;

	t = _newNode(a[mid]); 
	Nodes[t].parent = parent;

	if(s < mid) _build(Nodes[t].son[LEFT], t, LEFT, s, mid - 1, a);
	if(mid < e) _build(Nodes[t].son[RIGHT], t, RIGHT, mid + 1, e, a);

	_pushUp(t);
	return;
}

// 初始化Nodes, capa典型的取值为(N+insert的节点数量)
void init(int capa){
	/// capa+3, 2个哨兵以及1个零节点
	Nodes.assign(capa + 3, {0, {0, 0}, 0, data_zero(), 0, value_zero(), lazy_zero()});
	toUsed = 0;
	return;
}

// 利用全局数组建树, 数组有效位置为[1...n], 但a[0]与a[n+1]也会被建入
// 如果无需初始化，则调用build(0, {0, 0})即可
void build(int n, const data_type a[]) {
    _build(Root, 0, 0, 0, n + 1, a);    
	return;
}

// 得到节点t的位置，可能的答案为[0, n+1]
// 这是一个内部函数，考虑了哨兵
int _idx(int t){
	assert(t < Nodes.size());
	/// 首先要pushDown，关键在于flip
	_pushDown(t);
    _splay(0, t);
    int son = Nodes[t].son[LEFT];
	if(son) return Nodes[son].size;
	return 0;
}

/// 在pos位置插入一个数据data, pos保证合法
void insert(int pos, const data_type & data) {
    int n = Nodes[Root].size - 2;
	assert(1 <= pos and pos <= n + 1); // n + 1 表示最后一个位置之后

	int t = _kth(Root, pos - 1);
	_splay(0, t); // 将pos-1旋到树根

	int tt = _kth(Root, pos);
	_splay(Root, tt); // 将pos旋到树根的右儿子

	/// 将新节点挂到根的右儿子的左儿子
	t = _newNode(data);
    _link(tt, LEFT, t);
	_pushUp(tt); _pushUp(Root);	
	return;
}

/// 删除区间[s, e]，参数保证合法
void remove(int s, int e) {
	int n = Nodes[Root].size - 2;
	assert(1 <= s and s <= e and e <= n);
    
	int t = _kth(Root, s - 1);
	_splay(0, t);

	int tt = _kth(Root, e + 1);
	_splay(Root, tt);

	Nodes[Nodes[tt].son[LEFT]].parent = 0;
	Nodes[tt].son[LEFT] = 0;
	_pushUp(tt); _pushUp(Root);
	return;
}

/// [s, e]区间内部循环右移k位
void rotate(int s, int e, int k) {
    if(0 == (k %= e - s + 1)) return;
	if(k < 0) k = e - s + 1 + k;
	assert(1 <= k and k <= e - s);

	/// 首先删除[e - k + 1, e]
	int t = _kth(Root, e - k);
	_splay(0, t);
	int tt = _kth(Root, e + 1);
	_splay(Root, tt);
	int son = Nodes[tt].son[LEFT];
	Nodes[tt].son[LEFT] = 0;
	_pushUp(tt); _pushUp(Root);

	/// 再把son插入到s位置
	t = _kth(Root, s - 1);
	_splay(0, t);
	tt = _kth(Root, s);
	_splay(Root, tt);

	_link(tt, LEFT, son);
	_pushUp(tt); _pushUp(Root);
	return;
}

/// 将[s, e]区间移动到pos位置开始, 
/// 原pos位置及以后的数依次后移
/// 调用者需保证pos不在[s, e]区间之中
void move(int s, int e, int pos) {
	int n = Nodes[Root].size - 2;
	assert(1 <= s and s <= e and e <= n);
	assert(1 <= pos and pos <= n + 1); // n + 1表示最后一个位置之后
	assert(pos < s or pos > e);

	int t = _kth(Root, s - 1);
	_splay(0, t);

	int tt = _kth(Root, e + 1);
	_splay(Root, tt);

	int son = Nodes[tt].son[LEFT];
	Nodes[tt].son[LEFT] = 0;
    _pushUp(tt); _pushUp(Root);

	/// 找pos的前一个位置
    t = _kth(Root, pos < s ? pos - 1 : pos - 1 - (e - s + 1));
	_splay(0, t);
    /// 找pos位置
	tt = _kth(Root, pos < s ? pos : pos - (e - s + 1));
	_splay(Root, tt);

	_link(tt, LEFT, son);
	_pushUp(tt); _pushUp(Root);
	return;
}

/// 翻转区间[s, e]
void reverse(int s, int e) {
	int n = Nodes[Root].size - 2;
	assert(1 <= s and s <= e and e <= n);

	int t = _kth(Root, s - 1);
	_splay(0, t);

	int tt = _kth(Root, e + 1);
	_splay(Root, tt);	

	t = Nodes[tt].son[LEFT];

	_dn_(t, lazy_zero(), 1);
	_pushUp(tt); _pushUp(Root);
	return;
}

/// 根据delta的内容修改[s, e]区间的内容，这个操作不改变区间本身的结构
void modify(int s, int e, const lazy_type & delta) {
	int n = Nodes[Root].size - 2;
	assert(1 <= s and s <= e and e <= n);

	int t = _kth(Root, s - 1);
	_splay(0, t);

	int tt = _kth(Root, e + 1);
	_splay(Root, tt);

	/// 根的右儿子的左儿子打标记
	int son = Nodes[tt].son[LEFT];
	assert(son);

	_dn_(son, delta, 0);
	_pushUp(tt); _pushUp(Root);
	return;
}

/// 查询[s, e]区间的信息
value_type query(int s, int e) {
	int n = Nodes[Root].size - 2;
	assert(1 <= s and s <= e and e <= n);
		
    int t = _kth(Root, s - 1);
	_splay(0, t);

	int tt = _kth(Root, e + 1);
	_splay(Root, tt);

	int son = Nodes[tt].son[LEFT];
	return Nodes[son].value;
}

/// 按层次遍历输出SplayTree, 注意要pushDown, 因此不是const
void disp(ostream & os) {
	os << "SplayTree " << Root << ":" << endl;
    queue<int> q;
	q.push(Root);
	while(not q.empty()){
		auto h = q.front(); q.pop();
		_pushDown(h);
		auto & n = Nodes[h];
		os << h << ": (" << n.son[LEFT] << ", " << n.son[RIGHT] << ")";
		os << ", size = " << n.size << ", data = " << n.data;
		os << ", info = " << n.value;
		os << endl;
		if(n.son[LEFT]) q.push(n.son[LEFT]);
		if(n.son[RIGHT]) q.push(n.son[RIGHT]);
	}
	return;
}

/// 中序遍历输出原始数组, 要pushDown
void dispInOrder(ostream & os) {
    function<void(int)> __dfs = [&, this](int u){
        this->_pushDown(u);
		auto & n = this->Nodes[u];
		int son = n.son[LEFT];
		if(son) __dfs(son);
		os << n.data << " ";
		if(son = n.son[RIGHT]) __dfs(son);
	};

	auto t = _kth(Root, 0);
	_splay(0, t);
	auto tt = _kth(Root, Nodes[Root].size - 1);
	_splay(Root, tt);
	t = Nodes[tt].son[LEFT];
	__dfs(t);
	os << std::endl;
	return;
}

};

